// 斐波那契数列满足最优子结构，并且子问题出现了重复，适用于 动态规划 进行求解

/**
 * 使用动态规划求解斐波那契数列
 */
function fa(n) {
    if (n <= 2) return 1
    let i, m = []
    m[1] = 1
    m[2] = 1
    for (i = 3; i <= n; i++) { // 自底向上保存子问题的解
        m[i] = m[i - 1] + m[i - 2]
    }
    return m[n]
}

/**
 * 递归实现 斐波那契数列
 * @param {*} n 
 */
function fb(n) {
    if (n <= 1) {
        return n
    } else {
        return fb(n - 1) + fb(n - 2)
    }
 }

console.log(fa(100))